#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <stack> 
using namespace std;

// EdgeNode 类的实现
EdgeNode::EdgeNode() : dest(-1), link(nullptr) {}
EdgeNode::EdgeNode(int d, EdgeNode* l) : dest(d), link(l) {}
EdgeNode::~EdgeNode() {}
int EdgeNode::getDest() { return dest; }
EdgeNode* EdgeNode::getNext() { return link; }
void EdgeNode::setDest(int d) { dest = d; }
void EdgeNode::setNext(EdgeNode* l) { link = l; }

// VertexNode 类的实现
VertexNode::VertexNode() : data('\0'), firstEdge(nullptr) {}
VertexNode::VertexNode(char d, EdgeNode* e) : data(d), firstEdge(e) {}
VertexNode::~VertexNode() {
    EdgeNode* current = firstEdge;
    while (current) {
        EdgeNode* temp = current;
        current = current->getNext();
        delete temp;
    }
}
char VertexNode::getData() { return data; }
EdgeNode* VertexNode::getFirstEdge() { return firstEdge; }
void VertexNode::setData(char d) { data = d; }
void VertexNode::setFirstEdge(EdgeNode* e) { firstEdge = e; }

// MyGraph 类的实现
MyGraph::MyGraph() : nodeNum(0), edgeNum(0), VexList(nullptr) {}
MyGraph::MyGraph(int nodes, int edges, char* names, int* starts, int* ends) 
    : nodeNum(nodes), edgeNum(edges) {
    VexList = new VertexNode[nodeNum];
    for (int i = 0; i < nodeNum; ++i) {
        VexList[i].setData(names[i]);
        VexList[i].setFirstEdge(nullptr);
    }
    for (int i = 0; i < edgeNum; ++i) {
        int start = starts[i];
        int end = ends[i];
        VexList[start].setFirstEdge(new EdgeNode(end, VexList[start].getFirstEdge()));
        VexList[end].setFirstEdge(new EdgeNode(start, VexList[end].getFirstEdge()));
    }
}
MyGraph::~MyGraph() {
    delete[] VexList;
}
int MyGraph::getNodeNum() { return nodeNum; }
int MyGraph::getEdgeNum() { return edgeNum; }

string MyGraph::printGraph() {
    ostringstream oss;
    for (int i = 0; i < nodeNum; ++i) {
        oss << VexList[i].getData() << ": ";
        EdgeNode* current = VexList[i].getFirstEdge();
        while (current) {
            oss << VexList[current->getDest()].getData();
            if (current->getNext()) {
                oss << " ";
            }
            current = current->getNext();
        }
        if (i < nodeNum - 1) {
            oss << "\n";
        }
    }
    return oss.str();
}

int MyGraph::getFirstNeighbor(int v, int* visited) {
    EdgeNode* current = VexList[v].getFirstEdge();
    while (current) {
        if (!visited[current->getDest()]) {
            return current->getDest();
        }
        current = current->getNext();
    }
    return -1;
}

int MyGraph::getNextNeighbor(int v, int w, int* visited) {
    EdgeNode* current = VexList[v].getFirstEdge();
    while (current) {
        if (current->getDest() == w) {
            current = current->getNext();
            break;
        }
        current = current->getNext();
    }
    while (current) {
        if (!visited[current->getDest()]) {
            return current->getDest();
        }
        current = current->getNext();
    }
    return -1;
}

void MyGraph::DFS(int v, int* visited, string& result) {
    visited[v] = 1;
    result += VexList[v].getData();
    result += " ";
    int neighbor = getFirstNeighbor(v, visited);
    while (neighbor != -1) {
        if (!visited[neighbor]) {
            DFS(neighbor, visited, result);
        }
        neighbor = getNextNeighbor(v, neighbor, visited);
    }
}

void MyGraph::BFS(int v, int* visited, string& result) {
    queue<int> q;
    q.push(v);
    visited[v] = 1;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result += VexList[current].getData();
        result += " ";
        int neighbor = getFirstNeighbor(current, visited);
        while (neighbor != -1) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = 1;
            }
            neighbor = getNextNeighbor(current, neighbor, visited);
        }
    }
}

string MyGraph::graph_DFS_Traverse() {
    string result;
    int* visited = new int[nodeNum]{0};
    for (int i = 0; i < nodeNum; ++i) {
        if (!visited[i]) {
            DFS(i, visited, result);
        }
    }
    delete[] visited;
    return result;
}

string MyGraph::graph_BFS_Traverse() {
    string result;
    int* visited = new int[nodeNum]{0};
    for (int i = 0; i < nodeNum; ++i) {
        if (!visited[i]) {
            BFS(i, visited, result);
        }
    }
    delete[] visited;
    return result;
}